
<!DOCTYPE html>
<html lang="zh">
<head>
    <meta charset="UTF-8">
    <meta name="description" content="一个（最大）二叉堆是一个具有最大堆特性的完全二叉树。二叉堆是可用于实现高效优先队列ADT的数据结构之一。在优先队中，每一个元素都有一个优先级并且一个高优先级的元素总是比低优先级的先出头（如果有一样的优先级，像普通队列一样先进先出）。试试点击ExtractMax()来看一个从上面随机的二叉堆中提取最大元素的演示动画。为了集中讨论我们的话题，我们设计的最大二叉堆的动画不允许重复的整数。点击&#39;下一页&#39;（在左上角）/按&#39;Page Down&#39;来翻页，用下拉菜单/按&#39;空格‘来跳到某一个页面，或者按&#39;X&#39;（右下角）/按’Esc‘来进入探索模式。">
    <meta name="keywords" content="最大/最小 二叉堆 优先队">

    <meta name="csrf-token" content="JSzsfyehdURwnYiG9arDR2Xt7UbDvydp1FQcd41D">
    <meta http-equiv="X-UA-Compatible" content="IE=EDGE">
    <meta property="og:image" content="https://visualgo.net/img/png/heap.png">
    <title>VisuAlgo - 二叉堆（优先队列）</title>
    <link rel="icon" href="https://visualgo.net/img/favicon.png" type="image/x-icon">
    <link rel="shortcut icon" href="https://visualgo.net/img/favicon.png" type="image/x-icon">
    <link rel="apple-touch-icon" href="https://visualgo.net/img/favicon.png">
    <link rel="apple-touch-icon" sizes="72x72" href="https://visualgo.net/img/favicon.png">
    <link rel="apple-touch-icon" sizes="114x114" href="https://visualgo.net/img/favicon.png">
    <link rel="stylesheet" type="text/css" href="https://visualgo.net/fonts/silkscreen/stylesheet.css">
    <link rel="stylesheet" type="text/css" href="https://visualgo.net/css/common.css">
    <link rel="stylesheet" href="https://visualgo.net/css/viz-1.0.1.css">
    <link rel="stylesheet" href="https://visualgo.net/css/visual.css">
    <link rel="stylesheet" href="https://visualgo.net/css/drawgraph.css">
    <style>
      #e-lecture {
        top: 45px;
        right: 130px;
        width: 400px;
        display: block;
        background: none;
        /*overflow: normal;*/
        white-space: normal;
        text-align: right;
        color: black; font-weight: bold; font-size: 20px;
      }
      .electure-prev, .electure-next { /* force update, copied from viz.css */
        position: absolute;
        /* bottom: -12px; */
        top: -20px;
        /*bottom: '';*/
        padding: 3px 8px;
        background: #999;
        color: white;
        cursor: pointer;
        border-radius: 2px;
      }
      .electure-prev {
        left: -10px;
        /* right: 30px; */
      }
      .electure-next {
        right: -10px;
        color: white;
      }
    </style>
    <style>
.execAction { padding: 5px 8px; }
.err { padding: 5px 0px; }
#actions-extras input {
  width: 35px;
  padding: 5px 8px 7px;
}

#createNlogN-input input, #createN-input input { width: 200px; }

.createNlogN { bottom: 173px; }
.createN { bottom: 146px; }
.insert { bottom: 119px; }
.extractmax { bottom: 92px; }
.heapsort { bottom: 65px; }

#sort-viz {
  width: 100%;
  text-align: center;
  overflow: hidden;
  padding-top: 30px;
  /*padding-top: 100px;*/
}
</style>
    <script>
      function changeURL() {
        var URL = window.location.href.split('/');
        var val = document.getElementById("Language").value;
        URL[3] = val;
        window.location.assign(URL.join('/'));
      }
    </script>
</head>
<body>
<div id="top-bar">
    <a href="http://www.comp.nus.edu.sg/~stevenha"><span class="colour" style="border: 1px solid green; border-radius: 25px;">7</span></a>&nbsp;&nbsp;&nbsp;
    <a id="home" href="/">Visu<span class="colour">Algo</span><span style="font-size: 40%">.net</span></a>
    /
    <select id="Language" onchange="changeURL()">
        <option value="en">en</option>
        <option value="zh" selected>zh</option>
        <option value="es">es</option>
        <option value="pt">pt</option>
        <option value="ru">ru</option>
        <option value="id">id</option>
        <option value="de">de</option>
        <option value="bn">bn</option>
        <option value="ja">ja</option>
        <option value="ko">ko</option>
        <option value="vi">vi</option>
    </select>
    /heap
    <span class="right-links" id="useraccount">Login</span>
    <span id="title">
<a id='title-heap' class='selected-viz'>二叉堆</a>
</span>
    <div id="mode-menu">
        <div id='mode-button' title='exploration'>示例模式 &#9663;</div>
        <div id='other-modes'>
            <a title='e-Lecture'>电子讲座模式</a>
        </div>
    </div>
</div>
<div id="dark-overlay"></div>
<div id="status" class="panel"><p></p></div>
<div id="status-hide" class="panel-hide"><img src="https://visualgo.net/img/arrow_white_right.png" alt=">" title="show/hide status panel" /></div>
<div id="codetrace" class="panel">
    <p id="code1" style="padding-top: 10px;"></p>
    <p id="code2"></p>
    <p id="code3"></p>
    <p id="code4"></p>
    <p id="code5"></p>
    <p id="code6"></p>
    <p id="code7" style="padding-bottom: 10px;"></p>
</div>
<div id="codetrace-hide" class="panel-hide"><img src="https://visualgo.net/img/arrow_white_right.png" alt=">" title="show/hide codetrace panel" /></div>
<div id="left-bar"></div>
<div id="right-bar"></div>
<div id="media-controls">
    <div id='speed-control'>减速<div id='speed-input'></div>加速</div>
    <span id="go-to-beginning" class="media-control-button" title="go to beginning" onclick=goToBeginning()><img src="https://visualgo.net/img/goToBeginning.png" alt="go to beginning"></span>
    <span id="previous" class="media-control-button" title="step backward" onclick=stepBackward()><img src="https://visualgo.net/img/prevFrame.png" alt="previous frame"></span>
    <span id="pause" class="media-control-button" title="pause" onclick=pause()><img src="https://visualgo.net/img/pause.png" alt="pause"></span>
    <span id="play" class="media-control-button" title="play" onclick=play()><img src="https://visualgo.net/img/play.png" alt="play"></span>
    <span id="next" class="media-control-button" title="step forward" onclick=stepForward()><img src="https://visualgo.net/img/nextFrame.png" alt="next frame"></span>
    <span id="go-to-end" class="media-control-button" title="go to end" onclick=goToEnd()><img src="https://visualgo.net/img/goToEnd.png" alt="go to end"></span>
    <div id="progress-bar" class="media-control-button"></div>
</div>
<div id='viz'></div>
<div id='current-action' class='panel'></div>
<div id='e-lecture' class='panel'></div>
<div id="overlay" hidden></div>
<div id="dropdown-temp-holder" hidden></div>
<div id="electure-1" class="electure-dialog" style="bottom:60px;left:50%;margin-left:-250px;width:500px;">
    一个（最大）二叉堆是一个具有<u>最大堆</u>特性的完全二叉树。<br>二叉堆是可用于实现高效<u>优先队列ADT</u>的数据结构之一。在优先队中，每一个元素都有一个优先级并且一个高优先级的元素总是比低优先级的先出头（如果有一样的优先级，像普通队列一样先进先出）。试试点击<span style="white-space: normal;"><span class="slide-actions" onclick="doButtonAction26()">ExtractMax()</span>来看一个从上面随机的二叉堆中提取最大元素的演示动画。</span><div><span style="white-space: normal;">为了集中讨论我们的话题，我们设计的最大二叉堆的动画不允许重复的整数。</span></div><div><span style="white-space: normal;">点击&#39;下一页&#39;（在左上角）/按&#39;Page Down&#39;来翻页，用下拉菜单/按&#39;空格‘来跳到某一个页面，或者按&#39;X&#39;（右下角）/按’Esc‘来进入探索模式。<br></span><div><br></div></div>
    <hr>
    <p><b>Remarks</b>: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.<br>
        Please <a href="https://visualgo.net/login"><u>login</u></a> if you are a repeated visitor or <a href="https://visualgo.net/login"><u>register</u></a> for an (optional) free account first.</p>
    <div id='electure-dropdown'>
        <select class="lecture-dropdown" style="width:100%">
            <option value="1">1. <span style="white-space: normal;">二叉堆（大优先）</span></option>
            <option value="1-1">&nbsp;&nbsp;&nbsp;1-1. 定义</option>
            <option value="1-2">&nbsp;&nbsp;&nbsp;1-2. 优先队 ADT（抽象数据类型）</option>
            <option value="1-3">&nbsp;&nbsp;&nbsp;1-3. 例子</option>
            <option value="1-4">&nbsp;&nbsp;&nbsp;1-4. NUS 课堂独享</option>
            <option value="1-5">&nbsp;&nbsp;&nbsp;1-5. 例子 - 继续上页</option>
            <option value="1-6">&nbsp;&nbsp;&nbsp;1-6. 优先队例子</option>
            <option value="1-7">&nbsp;&nbsp;&nbsp;1-7. 潜在答案</option>
            <option value="1-8">&nbsp;&nbsp;&nbsp;1-8. 线性的数据结构来做优先队？</option>
            <option value="1-9">&nbsp;&nbsp;&nbsp;1-9. 答案 - 第一部分</option>
            <option value="1-10">&nbsp;&nbsp;&nbsp;1-10. 答案 - 第二部分<br></option>
            <option value="2">2. 动画 + 最大堆特性复习</option>
            <option value="2-1">&nbsp;&nbsp;&nbsp;2-1. 二叉堆的高度是 <span style="white-space: normal;">O(log N)</span></option>
            <option value="2-2">&nbsp;&nbsp;&nbsp;2-2. 以1为首元素的紧凑数组</option>
            <option value="3">3. 二叉堆（大优先） 操作</option>
            <option value="3-1">&nbsp;&nbsp;&nbsp;3-1. 那些额外的操作是什么？</option>
            <option value="4">4. <span style="white-space: normal;">Insert(v)&nbsp; &nbsp;//插入v</span><br></option>
            <option value="4-1">&nbsp;&nbsp;&nbsp;4-1. 为什么这样是正确的？</option>
            <option value="4-2">&nbsp;&nbsp;&nbsp;4-2. 答案</option>
            <option value="4-3">&nbsp;&nbsp;&nbsp;4-3. 时间复杂度分析</option>
            <option value="4-4">&nbsp;&nbsp;&nbsp;4-4. 答案</option>
            <option value="5">5. <span style="white-space: normal;">ExtractMax()&nbsp; &nbsp;//提取最大元素</span><br></option>
            <option value="5-1">&nbsp;&nbsp;&nbsp;5-1. 为什么和比较大的子项比较？</option>
            <option value="5-2">&nbsp;&nbsp;&nbsp;5-2. 答案</option>
            <option value="5-3">&nbsp;&nbsp;&nbsp;5-3. 时间复杂度分析</option>
            <option value="5-4">&nbsp;&nbsp;&nbsp;5-4. 答案</option>
            <option value="6">6. 用二叉堆来实现高效的优先队</option>
            <option value="7">7. <span style="white-space: normal;">Create(A) - 两种版本</span></option>
            <option value="7-1">&nbsp;&nbsp;&nbsp;7-1. <span style="white-space: normal;">Create(A) - O(N log N)</span><br></option>
            <option value="7-2">&nbsp;&nbsp;&nbsp;7-2. <span style="white-space: normal;">Create(A) - O(N)</span><br></option>
            <option value="7-3">&nbsp;&nbsp;&nbsp;7-3. 很多叶元素（叶顶点）</option>
            <option value="7-4">&nbsp;&nbsp;&nbsp;7-4. 为什么是 O(N)? - 第一部分</option>
            <option value="7-5">&nbsp;&nbsp;&nbsp;7-5. 为什么是 O(N)? - 第二部分</option>
            <option value="8">8. <span style="white-space: normal;">HeapSort()&nbsp; &nbsp;//堆排序</span><br></option>
            <option value="8-1">&nbsp;&nbsp;&nbsp;8-1. 讨论</option>
            <option value="8-2">&nbsp;&nbsp;&nbsp;8-2. 答案</option>
            <option value="9">9. 一些额外内容</option>
            <option value="9-1">&nbsp;&nbsp;&nbsp;9-1. 简单的最大堆 -&gt; 最小堆 转换</option>
            <option value="9-2">&nbsp;&nbsp;&nbsp;9-2. 源代码</option>
            <option value="9-3">&nbsp;&nbsp;&nbsp;9-3. 在线测试</option>
            <option value="9-4">&nbsp;&nbsp;&nbsp;9-4. 在线评审练习</option>
            <option value="9-5">&nbsp;&nbsp;&nbsp;9-5. 讨论</option>
            <option value="9-6">&nbsp;&nbsp;&nbsp;9-6. 令人震惊的东西</option>
            <option value="9-7">&nbsp;&nbsp;&nbsp;9-7. 令人震惊的东西 - 接上页</option>
            <option value="99">99. 状态面板</option>
            <option value="99-1">&nbsp;&nbsp;&nbsp;99-1. 代码追踪面板</option>
            <option value="99-2">&nbsp;&nbsp;&nbsp;99-2. 媒体控制</option>
            <option value="99-3">&nbsp;&nbsp;&nbsp;99-3. 返回 ”探索模式“</option>
        </select>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-next' data-nextid="1-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-1" class="electure-dialog" style="top:290px;left:50%;margin-left:-250px;width:500px;">
    <p><b>完整二叉树</b>: 每一层都是二叉树 都被填满 ，除了最低/最下面的一层，并且所有的最底层顶点都尽力向左靠拢。</p><br><p><b>最大二叉堆特性</b>: 每个顶点的父元素 - 除了根元素 - 都比当前元素的值要大。这种定义比下面这种更容易验证：一个顶点的值 - 除了叶顶点 - 必须必它的一个或者两个子元素要大。</p>
    <hr>
    <p>Pro-tip: Since you are not <a href="https://visualgo.net/login"><u>logged-in</u></a>, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: <b>[PageDown]</b> to advance to the next slide, <b>[PageUp]</b> to go back to the previous slide, <b>[Esc]</b> to toggle between this e-Lecture mode and exploration mode.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-2" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <p>优先队 (PQ) 抽象数据结构 (ADT) 和普通的队列 ADT 差不多, 但是它多了以下两个主要操作:</p><ol><li>Enqueue(<b>x</b>): 放一个新元素 (键值) <b>x</b> 进去优先队 (相同顺序)，</li><li><b>y</b> = Dequeue(): 返回已经在优先队里的有着最高优先级（键值）的元素 <b>y</b> 如果存在并列情况，返回先入队的那个。也就是说像一个正常的 <u><a href="https://visualgo.net/translation/zh/heap/none/all/list?mode=Queue">Queue</a> 那样 先进先出(FIFO)</u></li></ol>
    <hr>
    <p>Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution <b>or larger</b> (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (<b>F11</b>) to enjoy this setup. However, you can use zoom-in (<b>Ctrl +</b>) or zoom-out (<b>Ctrl -</b>) to calibrate this.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-3" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <p>想象：你是一个在机场控制塔工作的 <a href="https://en.wikipedia.org/wiki/Air_traffic_controller" target="_blank"><u>空中交通管理员 (ATC)</u></a> </p><p>你已经安排了飞机 X/Y 在接下来的 3/6 分钟分别降落。两辆飞机都有足够飞行15分钟的油并且都在距机场2分钟的位置。据你观察机场跑道现在空旷。</p><p>如果你不知道的话，飞机可以听令在机场附近飞 <u><a href="https://en.wikipedia.org/wiki/Holding_(aeronautics)" target="_blank">等待航线</a></u> 直到指定的降落时间。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-4" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    你要参加NUS的课程才会发现接下来会发生什么...<div>以下两种选择，你必须要做决定：</div><div><ol><li>举手并且挥手 代表你选择选项1，</li><li>举手但是不挥手代表你选择选项2，</li></ol></div><p>如果两种选项你都觉得不对，什么也不做就好了</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-5">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-5" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-6">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-6" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    除了你刚才看到的几个例子外（NUS课堂独享） 现实生活中还有很多可以用到优先队ADT的地方。<div>讨论：你能提出一些其他的在生活中能用到优先队的地方吗？</div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-5">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-7">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-7" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-6">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-8">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-8" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    我们可以用数组（头尾相连数组）或者链表来构造优先队ADT（抽象数据结构）但是入列队和出列队会比较慢 <span style="white-space: normal;">&nbsp;O(</span><b style="white-space: normal;">N</b><span style="white-space: normal;">)&nbsp;</span><div><span style="white-space: normal;">&nbsp;</span></div><div><span style="white-space: normal;">讨论：为什么？</span></div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-7">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-9">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-9" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-8">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="1-10">下一个 <u>PgDn</u></div>
</div>
<div id="electure-1-10" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-9">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-2" class="electure-dialog" style="top:290px;left:50%;margin-left:-250px;width:500px;">
    现在，我们来看上面的随机的最大二叉堆的动画。你应该看到一个完整的二叉树，除了根的所有顶点满足最大堆特性（<span style="white-space: normal;">A[parent(i)] &gt; A[i] - 记住我们不允许重复的整数）。</span><div><span style="white-space: normal;"><input class="mcq-answer" id="mcq-answer-6" value="32" hidden><p>Quiz: <b>Based on this Binary (Max) Heap property, where will the largest integer be located?</b></p><form><input type="radio" name="mcq-6-choice" value="32"> At the root<br><input type="radio" name="mcq-6-choice" value="34"> Can be anywhere<br><input type="radio" name="mcq-6-choice" value="33"> At one of the leaf<br></form><button class="mcq-submit" id="submit-6">Submit</button> <span id="answer-status-6"></span></span><span style="white-space: normal;"><br></span></div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="1-10">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="2-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-2-1" class="electure-dialog" style="top:290px;left:50%;margin-left:-250px;width:500px;">
    要记住的重要知识点：如果我们有一个含有N个元素的二叉堆，因为我们要把它储存成一个完整的二叉树，所以他的高度不会高过 <span style="white-space: normal;">O(log&nbsp;</span><b style="white-space: normal;">N</b><span style="white-space: normal;">)</span><div><span style="white-space: normal;">简单分析：一个满的（不止是完整的）含有N个元素的二叉树的高度 h 总是&nbsp;</span><b style="white-space: normal;">N = 2<sup>(h+1)</sup>-1，</b><span style="white-space: normal;">所以</span><b style="white-space: normal;">&nbsp;</b><b style="white-space: normal;">h = log<sub>2</sub>(N+1)-1 ~= log<sub>2</sub>&nbsp;N。</b></div><div><span style="white-space: normal;">看上面的例子&nbsp;</span><b style="white-space: normal;">N = 7 = 2<sup>(2+1)</sup>-1</b><span style="white-space: normal;">&nbsp;或者&nbsp;</span><b style="white-space: normal;">h = log<sub>2</sub>(7+1)-1 = 2</b><span style="white-space: normal;">.</span></div><div><span style="white-space: normal;">对于有关二叉堆的操作 以上知识点很重要。</span></div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="2-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-2-2" class="electure-dialog" style="top:290px;left:50%;margin-left:-250px;width:500px;">
    <p>一个完整的二叉树可以被存在一个紧凑数组A中 因为一个完整的数组和一个完整的二叉树一样 中间都没有空隙。为了简化下面的导航操作，我们用以1开始的数组。VisuAlgo 用在每一个顶点下面的 <font color="#ff0000">红色标识</font> 来标识顶点的序号。从1 到 N顺序读这些需要，你会看到这个完整二叉树的所有的元素 从上到下，从左到右。</p>这样，我们可以用操作序号的方式实现简单的二叉树遍历操作（运用简单的 <a href="./bitmask"><u>位移操作</u></a>):<ol><li>parent(i) = i&gt;&gt;1, 序号 i 除以二 (整数除法),</li><li>left(i) = i&lt;&lt;1, 序号 i 乘 2,</li><li>right(i) = (i&lt;&lt;1)+1, 序号 i 乘 2 再加 1.</li></ol>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="2-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-3" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p>在这个动画里，你可以使用以下五(5)种标准的最大二叉堆操作：</p><ol><li><b>Insert(v)</b> - O(log <b>N</b>)</li><li><b>ExtractMax()</b> - O(log <b>N</b>)</li><li><b>Create(A)</b> - O(<b>N</b> log <b>N</b>) 版本</li><li><b>Create(A)</b> - O(<b>N</b>) 版本</li><li><b>HeapSort()</b> - O(<b>N</b> log <b>N)</b></li></ol><p>最大二叉堆还有其他的操作（方法），但是因为NUS的课程标准里面并不包含更多的操作 所以我们暂时不做详细讨论。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="2-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="3-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-3-1" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-4" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>Insert(v)</b>: 当我们在往最大二叉堆插入元素 <b>v</b> 的时候 我们只能插入到最后一个元素<i> <b>N</b> + 1</i> 来维持一个紧凑的数组 = 完整二叉树特性。然而 最大堆的特性仍然可能没被满足。这时我们从插入点往上去修复最大堆特性（如果需要的话）直到整个堆符合最大堆特性。现在点 <span class="slide-actions" onclick="doButtonAction27()">Insert(v)</span> 几次来插入几个随机的 <b>v</b> 进去现在显示的最大二叉堆。</p><br><p>这个向上走并且修复最大堆特性的操作没有公认的名字。我们叫它 <b>ShiftUp</b> （上移）但是还有人叫它 <b>BubbleUp</b> 或者 <b>IncreaseKey</b> 操作.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="3-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="4-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-4-1" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    你明白为什么当你插入的新元素违反了最大堆的特性的时候 从插入点（第N+1个元素）往上（最多上到根元素）走，把当前顶点和它的父顶点换位 永远是正确的方法？
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="4-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-4-2" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="4-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="4-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-4-3" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>Insert(v)</b> 的时间复杂度是 O(log <b>N</b>)。</p><p>你理解这个推论吗？</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="4-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="4-4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-4-4" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="4-3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="5">下一个 <u>PgDn</u></div>
</div>
<div id="electure-5" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>ExtractMax()</b>: 提取并删除最大二叉堆中的最大元素（根）的操作需要一个在堆中的元素来替换根，不然最大堆（一个完整的二叉树，在中文中的&#39;林‘）会变成两个断开的子树（中文中两个&#39;木’）。这同样也是这个元素必须是最后一个元素N的原因：维持紧凑数组 = 完整二叉树性质。</p><p>因为我们要把最大二叉堆中的一个叶顶点晋升成根顶点，它很可能是会违背最大堆特性。ExtractMax() 这时从根往下比较当前值和它的两个子元素的值（如果必要的话）来修复最大二叉堆特性。现在在当前显示的最大二叉堆中试试 <span class="slide-actions" onclick="doButtonAction26()">ExtractMax()</span></p><p>这个向下走并修复最大堆特性的操作没有公认的名字。我们叫它 <b>ShiftDown</b> （下移）但是还有人叫它 <b>BubbleDown</b> 或者 <b>Heapify</b> 操作。.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="4-4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="5-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-5-1" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    在向下运动修复最大堆特性的时候，为什么当一个顶点有两个子元素的时候，我们必须检查（甚至交换）它两个子元素中较大的那个？<div>为什么我们不能只比较左（或者右，如果存在的话）顶点？</div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="5">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="5-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-5-2" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="5-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="5-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-5-3" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>ExtractMax()</b> 的时间复杂度是 O(log <b>N</b>)。</p><p>你理解这个推论吗？</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="5-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="5-4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-5-4" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="5-3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="6">下一个 <u>PgDn</u></div>
</div>
<div id="electure-6" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <p>到这里为止，我们有一个数据结构可以高效实现优先队ADT的两个主要操作：<br></p><ol><li><b>Enqueue(x)</b>, 可以用 <b>Insert(x)</b> 它花费 O(log <b>N</b>) 的时间</li><li><b>y</b> = Dequeue(), 可以用 <b>y = ExtractMax()</b> 它花费 O(log <b>N</b>) 的时间.</li></ol><p>然而用二叉堆的话 我们可以做一些其他的操作。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="5-4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>Create(A)</b>: 用含有 N 个逗号分隔的数组 A 从一个空的最大二叉堆开始创建一个合法的最大二叉堆</p><br><p>有两种方法完成创建操作一个简单但是慢 -&gt; O(<b>N</b> log <b>N</b>) 另一个用更复杂的技术但是快 -&gt; O(<b>N</b>).</p><br><p>教你一招：在两个浏览器里面同时打开 VisuAlgo。用最差情况 &#39;已排序例子&#39; 去执行不同版本的 Create(A)，你会看到可怕的差距。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="6">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7-1" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>Create(A) - O(N log N)</b>: 单纯的一个接一个的插入 (用 <b>Insert(v) </b>操作的意思) 所有 <b>N</b> 个在输入数组中的元素进入到一个本来是空的最大二叉堆中。</p><p><b>分析</b>: 这个操作显然是 O(<b>N</b> log <b>N</b>) 我们用了 O(log <b>N</b>) <b>Insert(v)</b> 操作 <b>N</b> 次. 让我们来研究 ’排好序的例子‘ 它是这个操作中比较复杂的例子之一（现在试试 <span class="slide-actions" onclick="doButtonAction23()">Hard Case - O(N log N)</span> 我们显示了这个例子 <b>A=[1,2,3,4,5,6,7]</b> -- 请耐心等待 这个例子会比较耗时). 如果我们用递增的顺序往一个空的最大二叉堆中插入，每一次插入都会触发一次从插入点（新叶元素）到根的上移操作。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7-2" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p><b>Create(A) - O(N)</b>: 更快的版本 <b>Create(A)</b> 操作是 Robert W. Floyd 在 1964年发明的。 它利用了紧凑数组的优势 = 完整的二叉树和所有的叶元素（顶点的一半）生来就是最大二叉堆。然后这个操作只从最后一个内顶点一路回到根元素来修复最大二叉堆特性（如果必要的话）。</p><br><p><b>分析</b>: 粗略分析我们得到 O(<b>N</b>/2 log <b>N</b>) = O(<b>N</b> log <b>N</b>) 但是它其实只是 O(2*<b>N</b>) = O(<b>N</b>) — 下面几页会讨论细节。现在试试 <span class="slide-actions" onclick="doButtonAction24()">Hard Case - O(N)</span> 用相同的输入数组 <b>A=[1,2,3,4,5,6,7]</b> 并且上一页那样观察（不是生成最多次调换的那个）这个版本要比 O(<b>N</b> log <b>N</b>) 版本厉害（快）得多.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7-3" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p>简单证明为什么在最大堆中（里面N个元素）一半的元素都是叶元素（为了概括性，我们假设N是奇数）：</p><p>架设最后一个叶元素的序号是 <b>N</b>, 那么它的父元素的序号是 <b>i = N/2 </b>(回忆 <a href="?slide=2-2"><u>这节课</u></a>). 它的左子元素的序号是 <b>i+1</b>, 如果存在的话 (它其实并不存在), 将会是 <b>2*(i+1) = 2*(N/2+1) = N+2</b>, 这个结果吵过了 <b>N</b> (最后一个叶元素) 所以 <b>i+1</b> 一定是一个没有子元素的叶元素。因为二叉堆的序号是连续的，所以序号s [<b>i+1 = N/2+1</b>, <b>i+2 = N/2+2</b>, ..., <b>N</b>], 或者说一半的顶点，都是叶元素。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7-4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7-4" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    首先，我们回忆含有<b>N</b>个元素的满二叉树的高度是<span style="white-space: normal;">log</span><sub style="white-space: normal;">2</sub><span style="white-space: normal;">&nbsp;</span><b style="white-space: normal;">N</b><span style="white-space: normal;">.</span><div><span style="white-space: normal;">其次，要明白运行</span><span style="font-family: monospace; white-space: normal;">shiftDown(i)操作所需要的时间不是最高值</span><span style="white-space: normal;">O(log&nbsp;</span><b style="white-space: normal;">N</b><span style="white-space: normal;">), 而是 O(</span><b style="white-space: normal;">h</b><span style="white-space: normal;">)，h是在以顶点 i 为跟的从树的高度。</span></div><div><span style="white-space: normal;">最后，在一个高度为 h 的满二叉树中 有</span><span style="font-family: monospace; white-space: normal;">ceil(N/2</span><sup style="font-family: monospace; white-space: normal;">h+1</sup><span style="font-family: monospace; white-space: normal;">)个顶点。</span></div><div><font face="monospace"><span style="white-space: normal;">在上面这个满二叉树的例子中</span></font><span style="white-space: normal;">&nbsp;</span><b style="white-space: normal;">N = 7，</b><span style="white-space: normal;">&nbsp;</span><b style="white-space: normal;">h = 2。</b><span style="white-space: normal;">&nbsp;顶点数量为&nbsp;</span><samp style="white-space: normal;">ceil(7/2<sup>0+1</sup>) = 4</samp><span style="white-space: normal;">&nbsp;分别是在</span><b style="white-space: normal;">h = 0 </b><span style="white-space: normal;">的</span><span style="white-space: normal;">&nbsp;{44,35,26,17} 。在高度</span><b style="white-space: normal;">h = 1</b><span style="white-space: normal;">有</span><samp style="white-space: normal;">ceil(7/2<sup>1+1</sup>) = 2</samp><span style="white-space: normal;">&nbsp;个顶点 分别是: {62,53} 在高度</span><b style="white-space: normal;">h = 2 </b><span style="white-space: normal;">有</span><span style="white-space: normal;">&nbsp;</span><samp style="white-space: normal;">ceil(7/2<sup>2+1</sup>) = 1</samp><span style="white-space: normal;">&nbsp;个顶点 它是 {71}。</span></div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7-3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="7-5">下一个 <u>PgDn</u></div>
</div>
<div id="electure-7-5" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p>Create(A) 用 O(<b>N</b>) 的版本是这样：</p><br><img src="https://visualgo.net/img/createheapanalysis.png" width="500" alt="analysis"><p><br></p><p>如果以上公式太复杂的话，现代学生会想到用 <a href="https://www.wolframalpha.com/input/?i=0%2F1%2B1%2F2%2B2%2F4%2B3%2F8%2B4%2F16%2B..." target="_blank"><u>WolframAlpha</u></a> 来解决。</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7-4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="8">下一个 <u>PgDn</u></div>
</div>
<div id="electure-8" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p>堆排序函数<b>HeapSort()</b><b>：</b> John William Joseph Williams 在1964年发明了<b>堆排序算法</b>和这个二叉堆数据结构. 堆排序的操作 （假定最大二叉堆已经在<b>O(n)</b>的时间复杂度内建立）非常简单。只需要调用提取堆顶函数<b>ExtractMax() </b>n次即可，每次的时间复杂度为<span style="white-space: normal;">O(log&nbsp;</span><b style="white-space: normal;">N</b><span style="white-space: normal;">)</span>. 现在你可以试一下屏幕上的这个最大二叉堆 <span style="white-space: normal;"><span class="slide-actions" onclick="doButtonAction25()">HeapSort()</span></span></p><br>分析：<b>堆排序</b>显然是<span style="white-space: normal;">O(</span><b style="white-space: normal;">N</b><span style="white-space: normal;">&nbsp;log&nbsp;</span><b style="white-space: normal;">N</b><span style="white-space: normal;">) - 一个最优的通过比较来排序的算法&nbsp;</span><span style="white-space: normal;"><input class="msq-answer" id="msq-answer-7" value="36,37,38" hidden><p>Quiz: <b>In worst case scenario, HeapSort() is asymptotically faster than...</b></p><input type="checkbox" class="msq-choice" id="msq-7-choice-38"> Insertion Sort<br><input type="checkbox" class="msq-choice" id="msq-7-choice-36"> Selection Sort<br><input type="checkbox" class="msq-choice" id="msq-7-choice-35"> Merge Sort<br><input type="checkbox" class="msq-choice" id="msq-7-choice-37"> Bubble Sort<br><button class="msq-submit" id="submit-7">Submit</button> <span id="answer-status-7"></span></span>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="7-5">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="8-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-8-1" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <p>尽管 <b>HeapSort()</b> 在最好/平均/最坏 情况下的时间复杂度都是 θ(<b>N</b> log <b>N</b>) ，它真的是最好的用比较元素的方法来实现的排序算法吗？</p> <br><p>讨论点：<b>HeapSort()</b>的缓存性能如何？</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="8">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="8-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-8-2" class="electure-dialog" style="bottom:220px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="8-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    现在你已经到了最大二叉堆基础知识这章的结尾 我们希望你可以在探索模式中探索更多。<div>然而我们还有一些更有趣的最大二叉堆的挑战 这些不在我们这章的大纲里。</div><p>当你全部学会了的时候，我们邀请你学习更高级的算法 它用优先队做底层数据结构（之一），例如 <a href="./mst" target="_blank"><u>Prim&#39;s MST algorithm</u></a>, <a href="./sssp" target="_blank"><u>Dijkstra&#39;s SSSP algorithm</u></a>, A* 搜索算法(还不在 VisuAlgo里), 等等.<br></p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="8-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-1" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-2" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <p>如果你在寻找一个最大二叉堆模型来构造优先队，好消息。</p><p>C++ 和 Java 已经有内置的优先队实现 它很有可能用的就是这个数据结构。他们是 <a href="http://en.cppreference.com/w/cpp/container/priority_queue" target="_blank"><u>C++ STL priority_queue</u></a> (默认的是最大优先队) 和 <a href="https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html" target="_blank"><u>Java PriorityQueue</u></a> (默认是最小优先队). 然而这些内置的实现不一定适合我们高效的做一些优先队的扩展操作（因为NUS课程的原因，这里不谈细节）</p><p>PS: 堆排序很可能会在 C++ STL 的 <u><a href="http://en.cppreference.com/w/cpp/algorithm/partial_sort" target="_blank">partial_sort</a></u>用到</p><hr><p>尽管如此，这里有我们的实现 <a href="http://www.comp.nus.edu.sg/~stevenha/cs2040c/demos/BinaryHeapDemo.cpp" target="_blank"><u>BinaryHeapDemo.cpp</u></a>.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-3" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    如果你想了解更多关于这个数据结构的有趣问题，你可以去这里做一些训练和测试 <a href="https://visualgo.net/training?diff=Medium&amp;n=7&amp;tl=0&amp;module=heap">二叉堆</a> （你不需要登录 但是只有简单和中等难度可以选）。<div>如果你是已经注册了的用户，请登录并且去 <a href="https://visualgo.net/training">训练主页</a> 通过这个单元的考试，相应的成就会被记录在你的账户里.</div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-2">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-4">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-4" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <p>我们还有一些编程问题可以用到二叉堆数据结构<a href="https://uva.onlinejudge.org/external/12/1203.pdf" title="" target="_blank"><u>UVa 01203 - Argus</u></a> 和 <a href="https://open.kattis.com/problems/numbertree" title="" target="_blank"><u>Kattis - numbertree</u></a>.</p><br><p>试着解决它们来提高你对这个数据结构的理解。你可以用C++ STL priority_queue或者JAVA PriorityQueue 如果它们可以简化你的解法</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-3">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-5">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-5" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-4">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-6">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-6" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-5">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="9-7">下一个 <u>PgDn</u></div>
</div>
<div id="electure-9-7" class="electure-dialog" style="top:60px;left:60px;width:500px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-6">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="99">下一个 <u>PgDn</u></div>
</div>
<div id="electure-99" class="electure-dialog" style="right:150px;bottom:335px;width:500px;">
    当操作进行时，状态面板将会有每个步骤的描述。
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="9-7">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="99-1">下一个 <u>PgDn</u></div>
</div>
<div id="electure-99-1" class="electure-dialog" style="right:170px;bottom:275px;width:180px;">
    <div style="background-color: white; color: black;">
        <p>e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature <b>and you are really a CS lecturer (show your University staff profile)</b>.</p>
    </div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="99">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="99-2">下一个 <u>PgDn</u></div>
</div>
<div id="electure-99-2" class="electure-dialog" style="bottom:70px;left:50%;margin-left:-120px;width:260px;">
    使用用户控件控制动画！可用的快捷键有：<div>空格键：绘制／停止／重绘</div><div>左／右箭头：上一步／下一步</div><div>-／+：减缓／增加速度</div><div><br></div>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="99-1">上一个 <u>PgUp</u></div>
    <div class='electure-next' data-nextid="99-3">下一个 <u>PgDn</u></div>
</div>
<div id="electure-99-3" class="electure-dialog" style="top:70px;right:60px;width:300px;">
    <p>Return to &#39;Exploration Mode&#39; to start exploring!</p><br><p>Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.</p>
    <div class='electure-end'>X <u>Esc</u></div>
    <div class='electure-prev' data-nextid="99-2">上一个 <u>PgUp</u></div>
</div>
<div id="popup" hidden>
    <div id="popup-content"></div>
    <span id="hide-popup" hidden>X <u>关闭</u></span>
</div>

<div
    style="text-align: center;font-size: 20px;color:#666;height: 100px;line-height: 50px;">
    <b>aserbao出品 </b>
    <h3>关注公众号「aserbaocool」获取免费学习资料</h3>
    <!--<marquee hspace=20 vspace=20 width=350 bgcolor=ffffff align=middle>关注公众号「aserbaocool」获取更多学习资料</marquee>-->
</div>

<div id="actions" class="panel">
    <p id="createNlogN">创建(A) - O(<b>N</b> log <b>N</b>)</p>
    <p id="createN">创建(A) - O(<b>N</b>)</p>
    <p id="insert">插入(v)</p>
    <p id="extractmax" class="execAction" onclick=extractmax()>提取最大值()</p>
    <p id="heapsort" class="execAction" onclick=heapsort()>堆排序()</p>
</div>
<div id="actions-hide" class="panel-hide"><img src="https://visualgo.net/img/arrow_white_right.png" alt=">" title="show/hide actions panel"></div>
<div id="actions-extras">
    <div class="createNlogN action-menu-pullout">
        <div id="createNlogN-input" class="new-menu-option">A = <input type="text" id="arrv1" autocomplete="off" value="2,7,26,25,19,17,1,90,3,36"></div>
        <div id="createNlogN-go" class="execAction coloured-menu-option" onclick="createNlogN()"><p>执行</p></div>
        <div id="createNlogN-sample" class="execAction new-menu-option coloured-menu-option" onclick="createNlogNSample()"><p>已排序的例子</p></div>
        <div id="createNlogN-random" class="execAction new-menu-option coloured-menu-option" onclick="createNlogNRandom()"><p>随机</p></div>
        <div id="createNlogN-err" class="err"></div>
    </div>
    <div class="createN action-menu-pullout">
        <div id="createN-input" class="new-menu-option">A = <input type="text" id="arrv2" autocomplete="off" value="2,7,26,25,19,17,1,90,3,36"></div>
        <div id="createN-go" class="execAction coloured-menu-option" onclick="createN()"><p>执行</p></div>
        <div id="createN-sample" class="execAction new-menu-option coloured-menu-option" onclick="createNSample()"><p>已排序的例子</p></div>
        <div id="createN-random" class="execAction new-menu-option coloured-menu-option" onclick="createNRandom()"><p>随机</p></div>
        <div id="createN-err" class="err"></div>
    </div>
    <div class="insert action-menu-pullout">
        <div id="insert-input" class="new-menu-option">v = <input type="number" id="v" autocomplete="off" min=0 value=26></div>
        <div id="insert-go" class="execAction coloured-menu-option" onclick="insert()"><p>执行</p></div>
        <div id="insert-err" class="err"></div>
    </div>
    <div class="extractmax action-menu-pullout">
        <div id="extractmax-err" class="err"></div>
    </div>
    <div class="heapsort action-menu-pullout">
        <div id="heapsort-err" class="err"></div>
    </div>
</div>
<div id="bottom-bar">
    <a id="trigger-about">关于</a>
    <a id="trigger-team">团队</a>
    <a id="trigger-terms">使用条款</a>
</div>
<div id="about" class="overlays">
    <h4>关于</h4><span class='close-overlay'>&#x2715;</span>
    <div class='content'>
        VisuAlgo在2011年由Steven Halim博士概念化，作为一个工具，帮助他的学生更好地理解数据结构和算法，让他们自己和自己的步伐学习基础。<br>VisuAlgo包含许多高级算法，这些算法在Steven Halim博士的书（“竞争规划”，与他的兄弟Felix Halim博士合作）和其他书中讨论。今天，一些高级算法的可视化/动画只能在VisuAlgo中找到。<br>虽然专门为新加坡国立大学（NUS）学生采取各种数据结构和算法类（例如CS1010，CS1020，CS2010，CS2020，CS3230和CS3230），作为在线学习的倡导者，我们希望世界各地的好奇心发现这些可视化也很有用。<br>VisuAlgo不是从一开始就设计为在小触摸屏（例如智能手机）上工作良好，因为需要满足许多复杂的算法可视化，需要大量的像素和点击并拖动手势进行交互。一个令人尊敬的用户体验的最低屏幕分辨率为1024x768，并且只有着陆页相对适合移动设备。<br>VisuAlgo是一个正在进行的项目，更复杂的可视化仍在开发中。<br>最令人兴奋的发展是自动问题生成器和验证器（在线测验系统），允许学生测试他们的基本数据结构和算法的知识。这些问题是通过一些规则随机生成的，学生的答案会在提交给我们的评分服务器后立即自动分级。这个在线测验系统，当它被更多的世界各地的CS教师采用，应该技术上消除许多大学的典型计算机科学考试手动基本数据结构和算法问题。通过在通过在线测验时设置小（但非零）的重量，CS教练可以（显着地）增加他/她的学生掌握这些基本问题，因为学生具有几乎无限数量的可以立即被验证的训练问题他们参加在线测验。培训模式目前包含12个可视化模块的问题。我们将很快添加剩余的8个可视化模块，以便VisuAlgo中的每个可视化模块都有在线测验组件。<br>另一个积极的发展分支是VisuAlgo的国际化子项目。我们要为VisuAlgo系统中出现的所有英语文本准备一个CS术语的数据库。这是一个很大的任务，需要众包。一旦系统准备就绪，我们将邀请VisuAlgo游客贡献，特别是如果你不是英语母语者。目前，我们还以各种语言写了有关VisuAlgo的公共注释：<br>
        <a href="https://weibo.com/p/230418436e9ee80102v4rk" target='_blank'><u>zh</u></a>, <a href='https://www.facebook.com/notes/steven-halim/httpidvisualgonet-visualisasi-struktur-data-dan-algoritma-dengan-animasi/10153236934439689' target='_blank'><u>id</u></a>, <a href="https://blog.naver.com/visualgo_nus" target='_blank'><u>kr</u></a>, <a href='https://www.facebook.com/groups/163215593699283/permalink/824003417620494/' target='_blank'><u>vn</u></a>, <a href='http://pantip.com/topic/32736343' target='_blank'><u>th</u></a>.</p>
    </div>
</div>
<div id="team" class="overlays">
    <h4>团队</h4><span class='close-overlay'>&#x2715;</span>
    <div class='content'>
        <p>
            <strong><span style='line-height: 150%;'>项目领导和顾问（2011年7月至今）</span></strong><br>
            <a href='http://www.comp.nus.edu.sg/~stevenha/' target='_blank'>Dr Steven Halim</a>, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)<br>
            <a href='http://felix-halim.net/' target='_blank'>Dr Felix Halim</a>, Software Engineer, Google (Mountain View)
        </p>
        <p>
            <strong><span style='line-height: 150%;'>本科生研究人员 1 (Jul 2011-Apr 2012)</span></strong><br>
            Koh Zi Chun, <a href='http://roticv.rantx.com/' target='_blank'>Victor Loh Bo Huai</a>
        </p>
        <p>
            <strong><span style='line-height: 150%;'>最后一年项目/ UROP学生 1 (Jul 2012-Dec 2013)</span></strong><br>
            Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
        </p>
        <p>
            <strong><span style='line-height: 150%;'>最后一年项目/ UROP学生 2 (Jun 2013-Apr 2014)</span></strong><br>
            <a href='http://www.rosemarietan.com/' target='_blank'>Rose Marie Tan Zhao Yun</a>, Ivan Reinaldo
        </p>
        <p>
            <strong><span style='line-height: 150%;'>本科生研究人员 2 (May 2014-Jul 2014)</span></strong><br>
            Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu
        </p>
        <p>
            <strong><span style='line-height: 150%;'>最后一年项目/ UROP学生 3 (Jun 2014-Apr 2015)</span></strong><br>
            Erin Teo Yi Ling, Wang Zi
        </p>
        <p>
            <strong><span style='line-height: 150%;'>最后一年项目/ UROP学生 4 (Jun 2016-Dec 2017)</span></strong><br>
            Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
        </p>
        <p>
            List of translators who have contributed &ge;100 translations can be found at <a href="https://visualgo.net/statistics">statistics</a> page.
        </p>
        <p>
            <strong><span style='line-height: 150%;'>致谢</span></strong><br>
            这个项目是由来自NUS教学与学习发展中心（CDTL）的慷慨的教学增进赠款提供的。
        </p>
    </div>
</div>
<div id="termsofuse" class="overlays">
    <h4>使用条款</h4><span class='close-overlay'>&#x2715;</span>
    <div class='content'>
        VisuAlgo是地球上的计算机科学社区免费。如果你喜欢VisuAlgo，我们对你的唯一的要求就是通过你知道的方式，比如：Facebook、Twitter、课程网页、博客评论、电子邮件等<b>告诉其他计算机方面的学生/教师：VisuAlgo网站的神奇存在</b>。<br>如果您是数据结构和算法<b>学生/教师</b>，您可以直接将此网站用于您的课程。如果你从这个网站拍摄截图（视频），你可以使用屏幕截图（视频）在其他地方，只要你引用本网站的网址（http://visualgo.net）或出现在下面的出版物列表中作为参考。但是，您不能下载VisuAlgo（客户端）文件并将其托管在您自己的网站上，因为它是剽窃。到目前为止，我们不允许其他人分叉这个项目并创建VisuAlgo的<b>变体</b>。使用（客户端）的VisuAlgo的离线副本作为您的个人使用是很允许的。<br>请注意，VisuAlgo的在线测验组件本质上具有沉重的服务器端组件，并且没有简单的方法来在本地保存服务器端脚本和数据库。目前，公众只能使用“培训模式”来访问这些在线测验系统。目前，“测试模式”是一个更受控制的环境，用于使用这些随机生成的问题和自动验证在NUS的实际检查。其他感兴趣的CS教练应该联系史蒂文如果你想尝试这样的“测试模式”。<br><b>出版物名单</b><br>这项工作在2012年ACM ICPC世界总决赛（波兰，华沙）和IOI 2012年IOI大会（意大利Sirmione-Montichiari）的CLI讲习班上进行了简要介绍。您可以点击此链接阅读我们2012年关于这个系统的文章（它在2012年还没有被称为VisuAlgo）。<br>这项工作主要由我过去的学生完成。最近的最后报告是：Erin，Wang Zi，Rose，Ivan。<br><b>错误申报或请求添加新功能</b><br>VisuAlgo不是一个完成的项目。 Steven Halim博士仍在积极改进VisuAlgo。如果您在使用VisuAlgo并在我们的可视化页面/在线测验工具中发现错误，或者如果您想要求添加新功能，请联系Dr Steven Halim博士。他的联系邮箱是他的名字加谷歌邮箱后缀：StevenHalim@gmail.com。<br>
    </div>
</div>

<script src="https://visualgo.net/js/jquery-3.3.1.min.js"></script>
<script>
      var PHP_DOMAIN = "";

      // surprise colour!
      // Referenced to in  home.js and viz.js also
      var colourArray = ["#52bc69", "#d65775"/*"#ed5a7d"*/, "#2ebbd1", "#d9513c", "#fec515", "#4b65ba", "#ff8a27", "#a7d41e"]; // green, pink, blue, red, yellow, indigo, orange, lime

      function disableScroll() { $('html').css('overflow', 'hidden'); }

      function enableScroll() { $('html').css('overflow', 'visible'); }

      function replaceAll(find, replace, str) { return str.replace(new RegExp(find, 'g'), replace); }

      function getColours() {
        var generatedColours = new Array();
        while (generatedColours.length < 4) {
          var n = (Math.floor(Math.random() * colourArray.length));
          if ($.inArray(n, generatedColours) == -1)
            generatedColours.push(n);
        }
        return generatedColours;
      }

      function isOn(value, position) {
        return (value>>position) & 1 === 1;
      }

      function customAlert(msg) {
        $('#custom-alert p').html(msg);
        var m = -1 * ($('#custom-alert').outerHeight()/2);
        $('#custom-alert').css('margin-top', m+'px');
        $('#dark-overlay').fadeIn(function() {
          $('#custom-alert').fadeIn(function() {
            setTimeout(function() {
              $('#custom-alert').fadeOut(function() {
                $('#dark-overlay').fadeOut();
              });
            }, 1000);
          });
        });
      }

      function showLoadingScreen() {
        $('#loading-overlay').show();
        $('#loading-message').show();
      }

      function hideLoadingScreen() {
        $('#loading-overlay').hide();
      }

      function commonAction(retval, msg) {
        //setTimeout(function() {
          if (retval) { // mode == "exploration" && // now not only for exploration mode, but check if this opens other problems
            $('#current-action').show();
            $('#current-action').html(mode == "exploration" ? msg : ("e-Lecture Example (auto play until done)<br>" + msg));
            $('#progress-bar').slider("option", "max", gw.getTotalIteration()-1);
            triggerRightPanels();
            isPlaying = true;
          }
        //}, 500);
      }

      function getQueryVariable(variable) {
        var query = window.location.search.substring(1);
        var vars = query.split('&');
        for (var i = 0; i < vars.length; i++) {
          var pair = vars[i].split('=');
          if (decodeURIComponent(pair[0]) == variable)
            return decodeURIComponent(pair[1]);
        }
        return "";
      }

      var generatedColours = getColours();
      var surpriseColour = colourArray[generatedColours[0]];
      var colourTheSecond = colourArray[generatedColours[1]];
      var colourTheThird = colourArray[generatedColours[2]];
      var colourTheFourth = colourArray[generatedColours[3]];

      $(function() {
        $('.links').css('background', surpriseColour);
        $('.right-links').css('background', surpriseColour);
        $('#login-go').css('background', surpriseColour);

        $('.colour').css("color", surpriseColour); // name
        $('h4').css("background-color", surpriseColour); // about, contact us etc. button background

        // title
        $('#title a').click(function() {
          $('#title a').removeClass('selected-viz');
          $(this).addClass('selected-viz');
          // temporary quick fix for Google Chrome Aug 2016 issue...
          setTimeout(function(){ document.body.style.zoom = "100.1%"; }, 100); // force resize/redraw...
          setTimeout(function(){ document.body.style.zoom = "100%"; }, 600);
        });

        // overlays stuffs
        $('#trigger-about').click(function() {
          if ($(window).width() > 600) {
            $('#dark-overlay').fadeIn(function() {
              $('#about').fadeIn();
            });
          }
          else
            alert('Sorry, this dialog is too big. Please load it on bigger screen');
        });

        $('#trigger-team').click(function() {
          if ($(window).width() > 600) {
            $('#dark-overlay').fadeIn(function() {
              $('#team').fadeIn();
            });
          }
          else
            alert('Sorry, this dialog is too big. Please load it on bigger screen');
        });

        $('#trigger-terms').click(function() {
          if ($(window).width() > 600) {
            $('#dark-overlay').fadeIn(function() {
              $('#termsofuse').fadeIn();
            });
          }
          else
            alert('Sorry, this dialog is too big. Please load it on bigger screen');
        });

        $('.close-overlay').click(function() {
          $('.overlays').fadeOut(function() {
            $('#dark-overlay').fadeOut();
          });
        });

        $('#dark-overlay').click(function() {
          $('.overlays').fadeOut();
          $('#dark-overlay').fadeOut();
        });

        $.get('/isloggedin', function(data) {
          var isLoggedIn = data['isloggedin'] == '1';
          var element;
          if (isLoggedIn) {
            // element = '<a onclick="verifyLogout()">登出</a>';
            element = '<a href="https://visualgo.net/profile">Profile</a>';
          }
          else {
            element = '<a href="https://visualgo.net/login">登录<br></a>'
          }
          $('#useraccount').html(element);
        });
      });

      function verifyLogout() {
        // Steven's remarks: use a better 'confirm' than the default :(
        var doesLogout = confirm('你确定要退出登录吗？');
        if (doesLogout == true) {
          window.location = "https://visualgo.net/logout";
        }
      }

      function checkLogin() {
        $.get('/checklogin', function(data) {
          var url = data['url'];
          window.location.href = '/' + url;
        });
      }

      (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
      })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

      ga('create', 'UA-1566631-4', 'auto');
      ga('send', 'pageview');
    </script>

<script src="https://visualgo.net/js/jquery-ui.min.js"></script>

<script src="https://visualgo.net/js/d3.min.js"></script>
<script src="https://visualgo.net/js/viz-1.0.3.js"></script>
<script src="https://visualgo.net/js/visualgo_print.js"></script>
<script src="/js/graph_library.js"></script>
<script>
      function runSlide(slide) {
        if (slide == '1') {
          $("#e-lecture").html("slide " + slide + " (" + 2 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-1') {
          $("#e-lecture").html("slide " + slide + " (" + 4 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-2') {
          $("#e-lecture").html("slide " + slide + " (" + 6 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-3') {
          $("#e-lecture").html("slide " + slide + " (" + 8 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-4') {
          $("#e-lecture").html("slide " + slide + " (" + 10 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-5') {
          $("#e-lecture").html("slide " + slide + " (" + 12 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-6') {
          $("#e-lecture").html("slide " + slide + " (" + 14 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-7') {
          $("#e-lecture").html("slide " + slide + " (" + 16 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-8') {
          $("#e-lecture").html("slide " + slide + " (" + 18 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-9') {
          $("#e-lecture").html("slide " + slide + " (" + 20 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '1-10') {
          $("#e-lecture").html("slide " + slide + " (" + 22 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '2') {
          $("#e-lecture").html("slide " + slide + " (" + 25 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '2-1') {
          $("#e-lecture").html("slide " + slide + " (" + 27 + "%)");
          hw.restoreArray([999999,71,62,53,44,35,26,17]);
          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '2-2') {
          $("#e-lecture").html("slide " + slide + " (" + 29 + "%)");
          hw.createRandom();
          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '3') {
          $("#e-lecture").html("slide " + slide + " (" + 31 + "%)");

          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '3-1') {
          $("#e-lecture").html("slide " + slide + " (" + 33 + "%)");

          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '4') {
          $("#e-lecture").html("slide " + slide + " (" + 35 + "%)");
          $("#insert").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '4-1') {
          $("#e-lecture").html("slide " + slide + " (" + 37 + "%)");
          $("#insert").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '4-2') {
          $("#e-lecture").html("slide " + slide + " (" + 39 + "%)");
          $("#insert").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '4-3') {
          $("#e-lecture").html("slide " + slide + " (" + 41 + "%)");
          $("#insert").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '4-4') {
          $("#e-lecture").html("slide " + slide + " (" + 43 + "%)");
          $("#insert").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '5') {
          $("#e-lecture").html("slide " + slide + " (" + 45 + "%)");
          closeCreateNlogN();
closeCreateN();
closeInsert();
closeHeapsort();
openExtractmax();
$("#extractmax").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '5-1') {
          $("#e-lecture").html("slide " + slide + " (" + 47 + "%)");
          closeCreateNlogN();
closeCreateN();
closeInsert();
closeHeapsort();
openExtractmax();
$("#extractmax").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '5-2') {
          $("#e-lecture").html("slide " + slide + " (" + 50 + "%)");
          closeCreateNlogN();
closeCreateN();
closeInsert();
closeHeapsort();
openExtractmax();
$("#extractmax").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '5-3') {
          $("#e-lecture").html("slide " + slide + " (" + 52 + "%)");
          closeCreateNlogN();
closeCreateN();
closeInsert();
closeHeapsort();
openExtractmax();
$("#extractmax").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '5-4') {
          $("#e-lecture").html("slide " + slide + " (" + 54 + "%)");
          closeCreateNlogN();
closeCreateN();
closeInsert();
closeHeapsort();
openExtractmax();
$("#extractmax").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '6') {
          $("#e-lecture").html("slide " + slide + " (" + 56 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7') {
          $("#e-lecture").html("slide " + slide + " (" + 58 + "%)");
          $("#createNlogN").addClass("menu-highlighted");
$("#createN").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7-1') {
          $("#e-lecture").html("slide " + slide + " (" + 60 + "%)");
          $("#createNlogN").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7-2') {
          $("#e-lecture").html("slide " + slide + " (" + 62 + "%)");
          $("#createN").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7-3') {
          $("#e-lecture").html("slide " + slide + " (" + 64 + "%)");
          $("#createN").click().addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7-4') {
          $("#e-lecture").html("slide " + slide + " (" + 66 + "%)");
          $("#createN").click().addClass("menu-highlighted");
hw.restoreArray([999999,71,62,53,44,35,26,17]);
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '7-5') {
          $("#e-lecture").html("slide " + slide + " (" + 68 + "%)");
          $("#createN").click().addClass("menu-highlighted");
hw.restoreArray([999999,71,62,53,44,35,26,17]);
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '8') {
          $("#e-lecture").html("slide " + slide + " (" + 70 + "%)");
          $("#heapsort").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '8-1') {
          $("#e-lecture").html("slide " + slide + " (" + 72 + "%)");
          $("#heapsort").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '8-2') {
          $("#e-lecture").html("slide " + slide + " (" + 75 + "%)");
          $("#heapsort").addClass("menu-highlighted");
          showActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9') {
          $("#e-lecture").html("slide " + slide + " (" + 77 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-1') {
          $("#e-lecture").html("slide " + slide + " (" + 79 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-2') {
          $("#e-lecture").html("slide " + slide + " (" + 81 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-3') {
          $("#e-lecture").html("slide " + slide + " (" + 83 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-4') {
          $("#e-lecture").html("slide " + slide + " (" + 85 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-5') {
          $("#e-lecture").html("slide " + slide + " (" + 87 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-6') {
          $("#e-lecture").html("slide " + slide + " (" + 89 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '9-7') {
          $("#e-lecture").html("slide " + slide + " (" + 91 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '99') {
          $("#e-lecture").html("slide " + slide + " (" + 93 + "%)");

          hideEntireActionsPanel();

          showStatusPanel();
          showCodetracePanel();

        }
        if (slide == '99-1') {
          $("#e-lecture").html("slide " + slide + " (" + 95 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '99-2') {
          $("#e-lecture").html("slide " + slide + " (" + 97 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
        if (slide == '99-3') {
          $("#e-lecture").html("slide " + slide + " (" + 100 + "%)");

          hideEntireActionsPanel();
          hideStatusPanel();
          hideCodetracePanel();

        }
      }

      window.onpopstate = function(event) {
        var slide = event.state['slide'];
        openSlide(slide, function() {
          runSlide(slide);
        });
      };

      function getUrlParameter(sParam) {
        var sPageURL = decodeURIComponent(window.location.search.substring(1)),
        sURLVariables = sPageURL.split('&'), sParameterName, i;

        for (i = 0; i < sURLVariables.length; i++) {
          sParameterName = sURLVariables[i].split('=');
          if (sParameterName[0] === sParam) return sParameterName[1] === undefined ? true : sParameterName[1];
        }
      };

      function pushState(slideValue) {
        var url = '/zh/heap';
        if (typeof slideValue != 'undefined' && slideValue != null) url += '?slide=' + slideValue;
        window.history.pushState({slide: slideValue}, "slide " + slideValue, url);
      }

      function showPopup(callback) {
        $('#popup').fadeIn(100, callback);
      }

      function hidePopup(callback) {
        $('#popup').fadeOut(100, callback);
      }

      function showOverlay() {
        $('#overlay').css('opacity', 0.5);
        $('#overlay').show();
      }

      function hideOverlay() {
        $('#overlay').hide();
        $("#e-lecture").html("");
      }

      function makeOverlayTransparent() {
        $('#overlay').css('opacity', 0);
      }

      function hideSlide(callback) {
        isPlaying = true;
        closeSlide(cur_slide, function() {
          makeOverlayTransparent();
          setTimeout(callback, 700); // don't immediately run the animation, wait for 500ms+ first
        });
      }

      function showSlide() {
        isPlaying = false;
        openSlide(cur_slide);
        showOverlay();
      }

      $(function() {
        var slide = getUrlParameter('slide');

        $.get('/hasvisited' + '/heap', function(data) {
          var hasVisited = data['hasvisited'] == '1';
          if (!hasVisited) {
            var postData = {
              '_token': 'JSzsfyehdURwnYiG9arDR2Xt7UbDvydp1FQcd41D',
              'page': '/heap'.substring(1),
            };

            $.post("/visitpage", postData, function(data) {
              // non critical request...
            });

            if (typeof slide != undefined && slide != null) {
              cur_slide = slide;
            }

            $("#mode-menu a").trigger("click");
          }
          else {
            if (typeof slide != undefined && slide != null) {
              cur_slide = slide;
              $('#mode-menu a').click();
            }
          }
        }).fail(function() {
          if (typeof slide != undefined && slide != null) {
            cur_slide = slide;
            $('#mode-menu a').click();
          }
        });

        $('.mcq-submit').click(function() {
          var questionId = parseInt($(this).attr('id').split('-')[1]);
          var answer = $('#mcq-answer-' + questionId).val();
          var userAnswer = $('input[type=radio][name=mcq-'+questionId+'-choice]:checked').val();

          if (answer === userAnswer) {
            $('#answer-status-' + questionId).html('<font color="green"><b>Correct!</b></font>');
          }
          else {
            $('#answer-status-' + questionId).html('<font color="red"><b>Wrong Answer! Try again...</b></font>');
          }
          $('#answer-status-' + questionId).show();
          setTimeout(function() {
            $('#answer-status-' + questionId).fadeOut(1000);
          }, 1000);
        });

        $('.msq-submit').click(function() {
          var questionId = parseInt($(this).attr('id').split('-')[1]);
          var answer = $('#msq-answer-' + questionId).val();

          var answers = [];
          $('input[type=checkbox][class=msq-choice]:checked').each(function() {
            answers.push($(this).attr('id').split('-')[3]);
          });
          answers.sort();
          var userAnswer = answers.join(',');

          if (answer === userAnswer) {
            $('#answer-status-' + questionId).html('<font color="green">Correct!</font>');
          }
          else {
            $('#answer-status-' + questionId).html('<font color="red">Wrong Answer! Try again...</font>');
          }
          $('#answer-status-' + questionId).show();
          setTimeout(function() {
            $('#answer-status-' + questionId).fadeOut(1000);
          }, 1000);
        });

        $('select.lecture-dropdown').change(function() {
          var nextSlide = $(this).val();
          openSlide(nextSlide, function() {
            runSlide(nextSlide);
            pushState(nextSlide);
          });
        });

        $('#hide-popup').click(function() {
          hidePopup();
        });

        $('#popup').hover(function() {
          $('#hide-popup').show();
        }, function() {
          $('#hide-popup').hide();
        });

        $('#electure-1 .electure-next').click(function() {
          hidePopup();
          runSlide('1-1');
          pushState('1-1');
        });

        $('#electure-1-1 .electure-next').click(function() {
          hidePopup();
          runSlide('1-2');
          pushState('1-2');
        });
        $('#electure-1-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('1');
          pushState('1');
        });

        $('#electure-1-2 .electure-next').click(function() {
          hidePopup();
          runSlide('1-3');
          pushState('1-3');
        });
        $('#electure-1-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-1');
          pushState('1-1');
        });

        $('#electure-1-3 .electure-next').click(function() {
          hidePopup();
          runSlide('1-4');
          pushState('1-4');
        });
        $('#electure-1-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-2');
          pushState('1-2');
        });

        $('#electure-1-4 .electure-next').click(function() {
          hidePopup();
          runSlide('1-5');
          pushState('1-5');
        });
        $('#electure-1-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-3');
          pushState('1-3');
        });

        $('#electure-1-5 .electure-next').click(function() {
          hidePopup();
          runSlide('1-6');
          pushState('1-6');
        });
        $('#electure-1-5 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-4');
          pushState('1-4');
        });

        $('#electure-1-6 .electure-next').click(function() {
          hidePopup();
          runSlide('1-7');
          pushState('1-7');
        });
        $('#electure-1-6 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-5');
          pushState('1-5');
        });

        $('#electure-1-7 .electure-next').click(function() {
          hidePopup();
          runSlide('1-8');
          pushState('1-8');
        });
        $('#electure-1-7 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-6');
          pushState('1-6');
        });

        $('#electure-1-8 .electure-next').click(function() {
          hidePopup();
          runSlide('1-9');
          pushState('1-9');
        });
        $('#electure-1-8 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-7');
          pushState('1-7');
        });

        $('#electure-1-9 .electure-next').click(function() {
          hidePopup();
          runSlide('1-10');
          pushState('1-10');
        });
        $('#electure-1-9 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-8');
          pushState('1-8');
        });

        $('#electure-1-10 .electure-next').click(function() {
          hidePopup();
          runSlide('2');
          pushState('2');
        });
        $('#electure-1-10 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-9');
          pushState('1-9');
        });

        $('#electure-2 .electure-next').click(function() {
          hidePopup();
          runSlide('2-1');
          pushState('2-1');
        });
        $('#electure-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('1-10');
          pushState('1-10');
        });

        $('#electure-2-1 .electure-next').click(function() {
          hidePopup();
          runSlide('2-2');
          pushState('2-2');
        });
        $('#electure-2-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('2');
          pushState('2');
        });

        $('#electure-2-2 .electure-next').click(function() {
          hidePopup();
          runSlide('3');
          pushState('3');
        });
        $('#electure-2-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('2-1');
          pushState('2-1');
        });

        $('#electure-3 .electure-next').click(function() {
          hidePopup();
          runSlide('3-1');
          pushState('3-1');
        });
        $('#electure-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('2-2');
          pushState('2-2');
        });

        $('#electure-3-1 .electure-next').click(function() {
          hidePopup();
          runSlide('4');
          pushState('4');
        });
        $('#electure-3-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('3');
          pushState('3');
        });

        $('#electure-4 .electure-next').click(function() {
          hidePopup();
          runSlide('4-1');
          pushState('4-1');
        });
        $('#electure-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('3-1');
          pushState('3-1');
        });

        $('#electure-4-1 .electure-next').click(function() {
          hidePopup();
          runSlide('4-2');
          pushState('4-2');
        });
        $('#electure-4-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('4');
          pushState('4');
        });

        $('#electure-4-2 .electure-next').click(function() {
          hidePopup();
          runSlide('4-3');
          pushState('4-3');
        });
        $('#electure-4-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('4-1');
          pushState('4-1');
        });

        $('#electure-4-3 .electure-next').click(function() {
          hidePopup();
          runSlide('4-4');
          pushState('4-4');
        });
        $('#electure-4-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('4-2');
          pushState('4-2');
        });

        $('#electure-4-4 .electure-next').click(function() {
          hidePopup();
          runSlide('5');
          pushState('5');
        });
        $('#electure-4-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('4-3');
          pushState('4-3');
        });

        $('#electure-5 .electure-next').click(function() {
          hidePopup();
          runSlide('5-1');
          pushState('5-1');
        });
        $('#electure-5 .electure-prev').click(function() {
          hidePopup();
          runSlide('4-4');
          pushState('4-4');
        });

        $('#electure-5-1 .electure-next').click(function() {
          hidePopup();
          runSlide('5-2');
          pushState('5-2');
        });
        $('#electure-5-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('5');
          pushState('5');
        });

        $('#electure-5-2 .electure-next').click(function() {
          hidePopup();
          runSlide('5-3');
          pushState('5-3');
        });
        $('#electure-5-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('5-1');
          pushState('5-1');
        });

        $('#electure-5-3 .electure-next').click(function() {
          hidePopup();
          runSlide('5-4');
          pushState('5-4');
        });
        $('#electure-5-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('5-2');
          pushState('5-2');
        });

        $('#electure-5-4 .electure-next').click(function() {
          hidePopup();
          runSlide('6');
          pushState('6');
        });
        $('#electure-5-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('5-3');
          pushState('5-3');
        });

        $('#electure-6 .electure-next').click(function() {
          hidePopup();
          runSlide('7');
          pushState('7');
        });
        $('#electure-6 .electure-prev').click(function() {
          hidePopup();
          runSlide('5-4');
          pushState('5-4');
        });

        $('#electure-7 .electure-next').click(function() {
          hidePopup();
          runSlide('7-1');
          pushState('7-1');
        });
        $('#electure-7 .electure-prev').click(function() {
          hidePopup();
          runSlide('6');
          pushState('6');
        });

        $('#electure-7-1 .electure-next').click(function() {
          hidePopup();
          runSlide('7-2');
          pushState('7-2');
        });
        $('#electure-7-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('7');
          pushState('7');
        });

        $('#electure-7-2 .electure-next').click(function() {
          hidePopup();
          runSlide('7-3');
          pushState('7-3');
        });
        $('#electure-7-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('7-1');
          pushState('7-1');
        });

        $('#electure-7-3 .electure-next').click(function() {
          hidePopup();
          runSlide('7-4');
          pushState('7-4');
        });
        $('#electure-7-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('7-2');
          pushState('7-2');
        });

        $('#electure-7-4 .electure-next').click(function() {
          hidePopup();
          runSlide('7-5');
          pushState('7-5');
        });
        $('#electure-7-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('7-3');
          pushState('7-3');
        });

        $('#electure-7-5 .electure-next').click(function() {
          hidePopup();
          runSlide('8');
          pushState('8');
        });
        $('#electure-7-5 .electure-prev').click(function() {
          hidePopup();
          runSlide('7-4');
          pushState('7-4');
        });

        $('#electure-8 .electure-next').click(function() {
          hidePopup();
          runSlide('8-1');
          pushState('8-1');
        });
        $('#electure-8 .electure-prev').click(function() {
          hidePopup();
          runSlide('7-5');
          pushState('7-5');
        });

        $('#electure-8-1 .electure-next').click(function() {
          hidePopup();
          runSlide('8-2');
          pushState('8-2');
        });
        $('#electure-8-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('8');
          pushState('8');
        });

        $('#electure-8-2 .electure-next').click(function() {
          hidePopup();
          runSlide('9');
          pushState('9');
        });
        $('#electure-8-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('8-1');
          pushState('8-1');
        });

        $('#electure-9 .electure-next').click(function() {
          hidePopup();
          runSlide('9-1');
          pushState('9-1');
        });
        $('#electure-9 .electure-prev').click(function() {
          hidePopup();
          runSlide('8-2');
          pushState('8-2');
        });

        $('#electure-9-1 .electure-next').click(function() {
          hidePopup();
          runSlide('9-2');
          pushState('9-2');
        });
        $('#electure-9-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('9');
          pushState('9');
        });

        $('#electure-9-2 .electure-next').click(function() {
          hidePopup();
          runSlide('9-3');
          pushState('9-3');
        });
        $('#electure-9-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-1');
          pushState('9-1');
        });

        $('#electure-9-3 .electure-next').click(function() {
          hidePopup();
          runSlide('9-4');
          pushState('9-4');
        });
        $('#electure-9-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-2');
          pushState('9-2');
        });

        $('#electure-9-4 .electure-next').click(function() {
          hidePopup();
          runSlide('9-5');
          pushState('9-5');
        });
        $('#electure-9-4 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-3');
          pushState('9-3');
        });

        $('#electure-9-5 .electure-next').click(function() {
          hidePopup();
          runSlide('9-6');
          pushState('9-6');
        });
        $('#electure-9-5 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-4');
          pushState('9-4');
        });

        $('#electure-9-6 .electure-next').click(function() {
          hidePopup();
          runSlide('9-7');
          pushState('9-7');
        });
        $('#electure-9-6 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-5');
          pushState('9-5');
        });

        $('#electure-9-7 .electure-next').click(function() {
          hidePopup();
          runSlide('99');
          pushState('99');
        });
        $('#electure-9-7 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-6');
          pushState('9-6');
        });

        $('#electure-99 .electure-next').click(function() {
          hidePopup();
          runSlide('99-1');
          pushState('99-1');
        });
        $('#electure-99 .electure-prev').click(function() {
          hidePopup();
          runSlide('9-7');
          pushState('9-7');
        });

        $('#electure-99-1 .electure-next').click(function() {
          hidePopup();
          runSlide('99-2');
          pushState('99-2');
        });
        $('#electure-99-1 .electure-prev').click(function() {
          hidePopup();
          runSlide('99');
          pushState('99');
        });

        $('#electure-99-2 .electure-next').click(function() {
          hidePopup();
          runSlide('99-3');
          pushState('99-3');
        });
        $('#electure-99-2 .electure-prev').click(function() {
          hidePopup();
          runSlide('99-1');
          pushState('99-1');
        });

        $('#electure-99-3 .electure-prev').click(function() {
          hidePopup();
          runSlide('99-2');
          pushState('99-2');
        });



        // temporary quick fix for Google Chrome Aug 2016 issue..., put at last part so that everything else has been loaded
        // setTimeout(function(){ document.body.style.zoom = "100.1%"; }, 500);
        // setTimeout(function(){ document.body.style.zoom = "100%"; }, 600);
        // I turn it off on 14 June 2018, seems 'ok'?
      });

      function doButtonAction23() {
        CUSTOM_ACTION('createNlogN', "1,2,3,4,5,6,7");
      }
      function doButtonAction24() {
        CUSTOM_ACTION('createN', "1,2,3,4,5,6,7");
      }
      function doButtonAction25() {
        CUSTOM_ACTION('heapsort');
      }
      function doButtonAction26() {
        CUSTOM_ACTION('extractmax');
      }
      function doButtonAction27() {
        CUSTOM_ACTION('random_insert');
      }
      function doButtonAction34() {
        CUSTOM_ACTION('insert_top');
      }

      function adjustPopupToImageSize() {
        var width = $('#popup-image').prop('width');
        var height = $('#popup-image').prop('height');
        $('#popup').width(width + 20);
        $('#popup').height(height + 20);
        if (width == 0 && height == 0) {
          setTimeout(adjustPopupToImageSize, 200);
        } else {
          showPopup();
        }
      }

      function POPUP_IMAGE(url) {
        $('#popup-content').html('<img id="popup-image" src="' + url + '">');
        adjustPopupToImageSize();
      }

      function URL(url) {
        window.open(url, '_blank');
      }

      // Implement these functions in each visualisation
      // This function will be called before entering e-Lecture Mode
      function ENTER_LECTURE_MODE() {}

      // This function will be called before returning to Explore Mode
      function ENTER_EXPLORE_MODE() {}

      // Lecture action functions
      function CUSTOM_ACTION(action, data, mode) {}
    </script>
<script type="text/javascript">
// Heap Widget
// original author: Steven Halim

var Heap = function() {
  var gw = new GraphWidget();

  /*
   * A: Internal representation of Heap in this object
   * It is a compact 1-based 1-dimensional array (ignoring index 0)
   * The parent/left child/right child can be computed via index manipulation
   *
   * Elements of A are ObjectPair objects, where first element is the value and the second element is the ID of the vertex SVG corresponding to the value
   */

  /*
   * Edge IDs are the index of the child element, so for example edge A[1]-A[2] will have ID "e2" (edge 2)
   * The edges will be set to not change when vertexes are interchanged
   * This eliminates the need to maintain an Adjacency Matrix / List
   */

  var coord = new Array();
  var A = new Array();
  var amountVertex = 0;
  var arr;

  initArrayRandom();
  init();

  var stateList = [];

  this.getGraphWidget = function() { return gw; };

  function parent(i) { return i>>1; } // Math.floor(i/2);

  function left(i) { return i<<1; } // i*2;

  function right(i) { return (i<<1)+1; } // i*2+1;

  this.IsMaxHeap = function(array) {
    for (var i = 1; i < array.length; i++)
      if (array[parent(i)] < array[i])
        return false;
   return true;
  }

  this.generate = function(array) {
    clearScreen();
    array.unshift(999999);
    A = [];
    for (var i = 0; i < array.length; i++) {
      A[i] = new ObjectPair(array[i], amountVertex); // testing layout, to leave the edges there for now
      amountVertex++;
    }
    init();
  };

  this.saveArray = function() {
    arr = new Array();
    for (var i = 0; i < A.length; i++)
      arr[i] = A[i].getFirst();
    return arr;
  }

  this.restoreArray = function(arr) {
    clearScreen();
    amountVertex = arr.length;
    A = [];
    for (var i = 0; i < amountVertex; i++)
      A[i] = new ObjectPair(arr[i], i);
    init();
  }

  function initArrayRandom() {
    A = [];
    amountVertex = 5 + Math.floor(Math.random()*11); // [5..15]
    A[0] = new ObjectPair(999999, 0);
    arr = new Array();
    for (var i = 1; i < amountVertex; i++) {
      var lb = 20;
           if (i == 1)           lb = 80;
      else if (i >= 2 && i <= 3) lb = 60;
      else if (i >= 4 && i <= 7) lb = 40;
      var newVal = lb + Math.floor(Math.random()*20); // [lb..lb+19]
      while ($.inArray(newVal, arr) != -1)
        newVal = lb + Math.floor(Math.random()*20);
      arr.push(newVal);
      A[i] = new ObjectPair(newVal, i);
    }
  }

  this.createRandom = function() {
    clearScreen();
    initArrayRandom();
    init();
  }

  function init() {
    var i, j;

    // compute vertex coordinates
    var vtx_count = 1; // 1-based indexing
    for (i = 0; i <= 4; i++) { // we limit our visualization to 4 levels only
      var entriesInThisLevel = 1<<i; // 2^i
      for (j = 0; j < entriesInThisLevel; j++) {
        coord[vtx_count] = new Array();
        coord[vtx_count][0] = (2*j + 1) * 900 / (2*entriesInThisLevel); // x Coordinate
        coord[vtx_count][1] = 50 + 40*i; // y Coordinate
        vtx_count++;
      }
    }

    for (i = 1; i < A.length; i++) // add vertices first
      gw.addVertex(coord[i][0], coord[i][1], A[i].getFirst(), A[i].getSecond(), true, i);

    for (i = 2; i < A.length; i++) { // then add edges, i is edge id
      parentVertex = A[parent(i)].getSecond();
      childVertex = A[i].getSecond();
      gw.addEdge(parentVertex, childVertex, i, EDGE_TYPE_UDE, 1, true);
    }
  }

  function clearScreen() {
    var i;
    for (i = 2; i < A.length; i++) // remove edges first
      gw.removeEdge(i);
    for (i = 1; i < A.length; i++) // then afterwards, remove vertices
      gw.removeVertex(A[i].getSecond());
    amountVertex = 0;
    A = []; // destroy old A, create new one
  }

  this.insert = function(vertexText, startAnimationDirectly, callback) {
    if (A.length > 31) {
      $('#insert-err').html('抱歉，已达到上限31');
      if (typeof callback == 'function') callback();
      return false;
    }

    for (i = 0; i < A.length; i++) {
      if (A[i].getFirst() == parseInt(vertexText)) {
        $('#insert-err').html('抱歉，堆中已经包含该值。包含重复值的堆无法演示TAT');
        if (typeof callback == 'function') callback();
        return false;
      }
    }

    if (startAnimationDirectly == true) {
      stateList = [];
      populatePseudocode(0);
    }

    var i, key, cs;
    if (A.length > 1) {
      cs = createState(A);
      cs["status"] = "当前最大二叉堆";
      cs["lineNo"] = !startAnimationDirectly ? 2 : 0;
      stateList.push(cs); // zero-th frame, the starting point
    }

    A[A.length] = new ObjectPair(parseInt(vertexText), amountVertex);
    amountVertex++;
    i = A.length-1;

    cs = createState(A);
    cs["vl"][A[i].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
    cs["status"] = vertexText + " 被插入到了紧凑的数组A后面.";
    cs["lineNo"] = !startAnimationDirectly ? 3 : [1, 2]; // differentiate O(N log N) build vs single insert
    stateList.push(cs); // first frame, highlight the newly inserted vertex

    while (i > 1 && A[parent(i)].getFirst() < A[i].getFirst()) {
      cs = createState(A);
      cs["vl"][A[i].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
      cs["vl"][A[parent(i)].getSecond()]["state"] = VERTEX_TRAVERSED;
      cs["status"] = A[parent(i)].getFirst() + ' < ' + A[i].getFirst() + ', 所以交换他们的位置.';
      cs["lineNo"] = 3;
      stateList.push(cs); // before swap

      var temp = A[i];
      A[i] = A[parent(i)];
      A[parent(i)] = temp;
      cs = createState(A);
      cs["vl"][A[i].getSecond()]["state"] = VERTEX_TRAVERSED;
      cs["vl"][A[parent(i)].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
      cs["status"] = A[parent(i)].getFirst() + ' <-> ' + A[i].getFirst() + ' 已经被交换了.';
      cs["lineNo"] = !startAnimationDirectly ? 3 : 4;
      stateList.push(cs); // record the successive vertex swap animation
      i = parent(i);
    }

    cs = createState(A); // record the final state of the heap after insertion to stop the highlights
    cs["vl"][A[i].getSecond()]["state"] = VERTEX_HIGHLIGHTED; // highlighted the successful insertion
    cs["status"] = vertexText + ' 已经被成功插入.';
    cs["lineNo"] = !startAnimationDirectly ? 3 : 0;
    stateList.push(cs);

    if (startAnimationDirectly) gw.startAnimation(stateList, callback);
    return true;
  }

  this.shiftDown = function(i, calledFrom) {
    while (i < A.length) {
      var maxV = A[i].getFirst(), max_id = i;
      if (left(i) < A.length && maxV < A[left(i)].getFirst()) {
        maxV = A[left(i)].getFirst();
        max_id = left(i);
      }
      if (right(i) < A.length && maxV < A[right(i)].getFirst()) {
        maxV = A[right(i)].getFirst();
        max_id = right(i);
      }

      if (max_id != i) {
        var cs = createState(A);
        cs["vl"][A[i].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
        cs["vl"][A[max_id].getSecond()]["state"] = VERTEX_TRAVERSED;
        cs["status"] = A[i].getFirst() + ' < ' + A[max_id].getFirst() + ', 所以交换他们的位置.';
        if (calledFrom == 'extractmax')
          cs["lineNo"] = [4, 5];
        else if (calledFrom == 'createN')
          cs["lineNo"] = [2, 3];
        else if (calledFrom == 'heapsort')
          cs["lineNo"] = 2;
        stateList.push(cs); // deal with affected edges first

        var temp = A[i];
        A[i] = A[max_id];
        A[max_id] = temp;
        cs = createState(A);
        cs["status"] = A[i].getFirst() + ' <-> ' + A[max_id].getFirst() + ' 已经被交换了.';
        if (calledFrom == 'extractmax')
          cs["lineNo"] = 6;
        else if (calledFrom == 'createN')
          cs["lineNo"] = [2, 3];
        else if (calledFrom == 'heapsort')
          cs["lineNo"] = 2;
        stateList.push(cs);

        i = max_id;
      }
      else
        break;
    }
  }

  this.getMax = function() { return A[1].getFirst(); }

  this.extractMax = function(startAnimationDirectly, callback) {
    if (A.length == 2) {
      $('#extractmax-err').html('抱歉，最大二叉堆只剩这一个元素了，再删就没有啦！.');
      if (typeof callback == 'function') callback();
      return false;
    }

    if (startAnimationDirectly == true) {
      stateList = [];
      populatePseudocode(1);
    }

    var cs = createState(A);
    cs["vl"][A[1].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
    cs["status"] = '根元素储存的是最大的元素.';
    cs["lineNo"] = !startAnimationDirectly ? 2 : 0; // heapsort vs standard extract
    stateList.push(cs); // highlight the root (max element)

    cs = createState(A);
    delete cs["vl"][A[1].getSecond()];
    var maxitem = A[1].getFirst();
    cs["status"] = '拿出根元素 ' + maxitem + '.';
    cs["lineNo"] = !startAnimationDirectly ? 2 : 1;
    stateList.push(cs); // move the root (max element) a bit upwards (to simulate 'extract max')

    if (A.length > 2) {
      cs = createState(A);
      delete cs["vl"][A[1].getSecond()];
      cs["status"] = '用最后一个叶元素替换根元素 ' + A[A.length-1].getFirst() + '.';
      cs["vl"][A[A.length-1].getSecond()]["state"] = VERTEX_HIGHLIGHTED; // highlighted the last leaf
      cs["lineNo"] = !startAnimationDirectly ? 2 : [2, 3];
      stateList.push(cs); // delete bottom-most right-most leaf (later, also remove its associated edge)
    }

    if (A.length > 2) {
      A[1] = A[A.length-1];
      A.splice(A.length-1, 1);
      cs = createState(A);
      cs["vl"][A[1].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
      cs["status"] = '新的根.';
      cs["lineNo"] = !startAnimationDirectly ? 2 : [2, 3];
      stateList.push(cs); // highlight the new root
    }

    this.shiftDown(1, !startAnimationDirectly ? 'heapsort' : 'extractmax');

    cs = createState(A);
    cs["status"] = 'ExtractMax() 已经完成<div>返回最大元素</div>: ' + maxitem + '.';
    cs["lineNo"] = !startAnimationDirectly ? 1 : 0;
    stateList.push(cs);

    if (startAnimationDirectly) gw.startAnimation(stateList, callback);
    return true;
  }

  this.heapSort = function(callback) {
    if (A.length == 2) {
      $('#heapsort-err').html('抱歉，最大二叉堆只剩这一个元素了，再删就没有啦！.');
      if (typeof callback == 'function') callback();
      return false;
    }

    populatePseudocode(2);
    res = []; // copy first
    for (var i = 1; i < A.length; i++)
      res[i-1] = A[i].getFirst();
    res.sort(function(a, b) { return a-b });

    stateList = [];
    var len = A.length-1;
    var partial = [];
    for (var i = 0; i < len; i++)
      partial[i] = -1;

    for (var i = 0; i < len-1; i++) { // except the last item (minor bug if not stopped here)
      partial[len-1-i] = A[1].getFirst();
      this.extractMax(false);
      cs = createState(A);
      cs["status"] = '部分排序的结果是 ' + partial + '.';
      cs["lineNo"] = 1;
      stateList.push(cs);
    }

    cs = createState(A);
    cs["status"] = '最终排序完成的结果是 ' + res + '.';
    cs["lineNo"] = 0;
    stateList.push(cs);

    gw.startAnimation(stateList, callback);
    return true;
  }

  this.createNlogN = function(arr, callback) {
    if (arr.length > 31) {
      $('#createNlogN-err').html('抱歉，不支持演示超过31个元素的最大二叉堆.');
      if (typeof callback == 'function') callback();
      return false;
    }

    populatePseudocode(3);
    clearScreen();
    var i, initValue = [999999, parseInt(arr[0])];
    stateList = [];

    var cs = createState(A);
    cs["status"] = '从一个空的二叉堆开始.';
    cs["lineNo"] = 1;
    stateList.push(cs);

    for (i = 0; i < initValue.length; i++) {
      A[i] = new ObjectPair(initValue[i], amountVertex);
      amountVertex++;
    }
    init();

    cs = createState(A);
    cs["status"] = arr[0] + ' 已经被插入了<div>它变成了新的根元素</div>.';
    cs["lineNo"] = [2, 3];
    stateList.push(cs);

    for (i = 1; i < arr.length; i++) // insert one by one
      this.insert(parseInt(arr[i]), false);

    cs = createState(A);
    cs["status"] = '已经成功从数组A创建了最大二叉堆: ' + arr + '.';
    cs["lineNo"] = 0;
    stateList.push(cs);

    gw.startAnimation(stateList, callback);
    return true;
  }

  this.createN = function(arr, callback) {
    if (arr.length > 31) {
      $('#createN-err').html('抱歉，不支持演示超过31个元素的最大二叉堆.');
      if (typeof callback == 'function') callback();
      return false;
    }

    populatePseudocode(4);
    clearScreen();
    var i, initValue = [999999];

    for (i = 0; i < arr.length; i++)
      initValue[i+1] = parseInt(arr[i]);

    for (i = 0; i < initValue.length; i++) {
      A[i] = new ObjectPair(initValue[i], amountVertex);
      amountVertex++;
    }
    init();

    stateList = [];
    var cs = createState(A);
    cs["status"] = '保持数组A本来的样子（一个完整的二叉树结构）.';
    cs["lineNo"] = 1;
    stateList.push(cs);

    for (i = Math.floor(arr.length/2); i >= 1; i--) { // check heap property one by one
      cs = createState(A);
      cs["vl"][A[i].getSecond()]["state"] = VERTEX_HIGHLIGHTED;
      cs["status"] = 'shiftDown(' + i + ') 来修正以此为根的份树的大优先二叉树特性（如果需要的话） ' + A[i].getFirst() + '.';
      cs["lineNo"] = [2, 3];
      stateList.push(cs);

      this.shiftDown(i, 'createN');
    }

    cs = createState(A);
    cs["status"] = '已经成功从数组A创建了最大二叉堆: ' + arr + '.';
    cs["lineNo"] = 0;
    stateList.push(cs);

    gw.startAnimation(stateList, callback);
    return true;
  }

  function createState(iH) {
    var s = {
      "vl": {},
      "el": {},
    };

    for (var i = 1; i < iH.length; i++) {
      var key = iH[i].getSecond();
      s["vl"][key] = {};
      s["vl"][key]["cx"] = coord[i][0];
      s["vl"][key]["cy"] = coord[i][1];
      s["vl"][key]["text"] = iH[i].getFirst();
      s["vl"][key]["extratext"] = i; // the vertex number
      s["vl"][key]["state"] = VERTEX_DEFAULT;
    }

    for (var i = 2; i < iH.length; i++) {
      s["el"][i] = {};
      s["el"][i]["vertexA"] = iH[parent(i)].getSecond();
      s["el"][i]["vertexB"] = iH[i].getSecond();
      s["el"][i]["type"] = EDGE_TYPE_UDE;
      s["el"][i]["weight"] = 1;
      s["el"][i]["state"] = EDGE_DEFAULT;
      s["el"][i]["animateHighlighted"] = false;
    }

    return s;
  }

  function populatePseudocode(act) {
    switch (act) {
      case 0: // Insert
        $('#code1').html('<span style="white-space: normal;">A[A.length] = v&nbsp; &nbsp;//储存v</span><br>');
        $('#code2').html('i = A.length-1');
        $('#code3').html('<span style="white-space: normal;">while (i &gt; 1 &amp;&amp; A[parent(i)] &lt; A[i])&nbsp; &nbsp;//循环</span><br>');
        $('#code4').html('&nbsp&nbsp<span style="white-space: normal;">swap(A[i], A[parent(i)])&nbsp; &nbsp; //交换位置</span><br>');
        $('#code5').html('// <b><a href="http://cpbook.net/#downloads" target="_blank">ch2_06_priority_queue.cpp/java</a></b>');
        $('#code6').html('');
        $('#code7').html('');
        break;
      case 1: // ExtractMax
        $('#code1').html('拿出 A[1]');
        $('#code2').html('A[1] = A[A.length-1]');
        $('#code3').html('i = 1; A.length--');
        $('#code4').html('while (i &lt; A.length)');
        $('#code5').html('&nbsp&nbspif A[i] < (L = i 的两个下级中较大的)');
        $('#code6').html('&nbsp&nbsp&nbsp&nbsp<span style="white-space: normal;">swap(A[i], L)&nbsp; &nbsp;//交换</span><br>');
        $('#code7').html('// <b><a href="http://cpbook.net/#downloads" target="_blank">ch2_06_priority_queue.cpp/java</a></b>');
        break;
      case 2: // HeapSort
        $('#code1').html('for (i = 0; i &lt; A.length; i++)   //遍历A');
        $('#code2').html('&nbsp&nbsp提取最大值()');
        $('#code3').html('// <b><a href="http://cpbook.net/#downloads" target="_blank">ch2_06_priority_queue.cpp/java</a></b>');
        $('#code4').html('');
        $('#code5').html('');
        $('#code6').html('');
        $('#code7').html('');
        break;
      case 3: // Create, O(N log N)
        $('#code1').html('从一个空的二叉堆开始');
        $('#code2').html('for (i = 0; i &lt; A.length; i++)  //遍历A');
        $('#code3').html('&nbsp&nbsp插入(A[i])');
        $('#code4').html('// <b><a href="http://cpbook.net/#downloads" target="_blank">ch2_06_priority_queue.cpp/java</a></b>');
        $('#code5').html('');
        $('#code6').html('');
        $('#code7').html('');
        break;
      case 4: // Create, O(N)
        $('#code1').html('数组A本来的样子');
        $('#code2').html('for (i = A.length/2; i &gt;= 1; i--)');
        $('#code3').html('&nbsp&nbsp<span style="white-space: normal;">shiftDown(i)&nbsp; //下移</span><br>');
        $('#code4').html('// <b><a href="http://cpbook.net/#downloads" target="_blank">ch2_06_priority_queue.cpp/java</a></b>');
        $('#code5').html('');
        $('#code6').html('');
        $('#code7').html('');
        break;
    }
  }
}



// Heap Actions
var actionsWidth = 150;
var statusCodetraceWidth = 370;

var isCreateNlogNOpen = false, isCreateNOpen = false, isInsertOpen = false, isExtractmaxOpen = false, isHeapsortOpen = false;

function opencreateNlogN() {
  if (!isCreateNlogNOpen){
    $('.createNlogN').fadeIn('fast');
    isCreateNlogNOpen = true;
  }
}

function closeCreateNlogN() {
  if (isCreateNlogNOpen) {
    $('.createNlogN').fadeOut('fast');
    $('#createNlogN-err').html("");
    isCreateNlogNOpen = false;
  }
}

function opencreateN() {
  if (!isCreateNOpen) {
    $('.createN').fadeIn('fast');
    isCreateNOpen = true;
  }
}

function closeCreateN() {
  if (isCreateNOpen) {
    $('.createN').fadeOut('fast');
    $('#createN-err').html("");
    isCreateNOpen = false;
  }
}

function openInsert() {
  if (!isInsertOpen) {
    $('.insert').fadeIn('fast');
    isInsertOpen = true;
  }
}

function closeInsert() {
  if (isInsertOpen) {
    $('.insert').fadeOut('fast');
    $('#insert-err').html("");
    isInsertOpen = false;
  }
}

function openExtractmax() {
  if (!isExtractmaxOpen) {
    $('.extractmax').fadeIn('fast');
    isExtractmaxOpen = true;
  }
}

function closeExtractmax() {
  if (isExtractmaxOpen) {
    $('.extractmax').fadeOut('fast');
    $('#extractmax-err').html("");
    isExtractmaxOpen = false;
  }
}

function openHeapsort() {
  if (!isHeapsortOpen) {
    $('.heapsort').fadeIn('fast');
    isHeapsortOpen = true;
  }
}

function closeHeapsort() {
  if (isHeapsortOpen) {
    $('.heapsort').fadeOut('fast');
    $('#heapsort-err').html("");
    isHeapsortOpen = false;
  }
}

function hideEntireActionsPanel() {
  closeCreateNlogN();
  closeCreateN();
  closeInsert();
  closeExtractmax();
  closeHeapsort();
  hideActionsPanel();
}



// local
$('#play').hide();
var hw = new Heap();
var gw = hw.getGraphWidget();

$(function() {
  var createHeap = getQueryVariable("create");
  if (createHeap.length > 0) {
    var newHeap = createHeap.split(",");
    if (hw.IsMaxHeap(newHeap)) // the input parameter is already a max heap
      hw.generate(newHeap); // just show
    else {
      $('#arrv2').val(createHeap);
      createN(); // not yet a max heap, build it fast
      stop();
    }
  }

  $('#createNlogN').click(function() {
    closeCreateN();
    closeInsert();
    closeExtractmax();
    closeHeapsort();
    opencreateNlogN();
  });

  $('#createN').click(function() {
    closeCreateNlogN();
    closeInsert();
    closeExtractmax();
    closeHeapsort();
    opencreateN();
  });

  $('#insert').click(function() {
    closeCreateNlogN();
    closeCreateN();
    closeExtractmax();
    closeHeapsort();
    openInsert();
  });

  $('#extractmax').click(function() {
    closeCreateNlogN();
    closeCreateN();
    closeInsert();
    closeHeapsort();
    openExtractmax();
  });

  $('#heapsort').click(function() {
    closeCreateNlogN();
    closeCreateN();
    closeInsert();
    closeExtractmax();
    openHeapsort();
  });
});

function createNlogNWithInput(input, callback) {
  commonAction(hw.createNlogN(input.split(","), callback), "创建(A) - O(N log N): " + input);
}

function createNlogN(callback) {
  if (isPlaying) stop();
  var input = $('#arrv1').val();
  createNlogNWithInput(input, callback);
}

function createNlogNSample(callback) {
  if (isPlaying) stop();
  var input = "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31";
  createNlogNWithInput(input, callback);
}

function createNlogNRandom(callback) {
  if (isPlaying) stop();
  var n = 7 + Math.floor(17*Math.random());
  var input = new Array();
  while (n > 0) {
    var newVal = 1 + Math.floor(98*Math.random());
    if ($.inArray(newVal, input) == -1) {
      input.push(newVal);
      n--;
    }
  }
  input = input.join(",");
  createNlogNWithInput(input, callback);
}

function createNWithInput(input, callback) {
  commonAction(hw.createN(input.split(","), callback), "创建(A) - O(N): " + input);
}

function createN(callback) {
  if (isPlaying) stop();
  var input = $('#arrv2').val();
  createNWithInput(input, callback);
}

function createNSample(callback) {
  if (isPlaying) stop();
  var input = "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31";
  createNWithInput(input, callback);
}

function createNRandom(callback) {
  if (isPlaying) stop();
  var n = 7 + Math.floor(17*Math.random());
  var input = new Array();
  while (n > 0) {
    var newVal = 1 + Math.floor(98*Math.random());
    if ($.inArray(newVal, input) == -1) {
      input.push(newVal);
      n--;
    }
  }
  input = input.join(",");
  commonAction(hw.createN(input.split(","), callback), "创建(A) - O(N): " + input);
}

function insert(callback) {
  if (isPlaying) stop();
  var input = parseInt($("#v").val());
  commonAction(hw.insert(input, true, callback), "插入 " + input);
  setTimeout(function() {
    var existing = hw.saveArray();
    var next_num = 1 + Math.floor(Math.random()*88);
    while (existing.includes(next_num)) next_num = 1 + Math.floor(Math.random()*88);
    $("#v").val(next_num); // randomized for next click between [1..89}, and it won't exist before (allow for a few more insertion of 90-99, still two digits)
  }, 500);
}

function insert_top(callback) {
  if (isPlaying) stop();
  var input = hw.getMax()+1; // always increase the top value by 1
  commonAction(hw.insert(input, true, callback), "插入 " + input);
  setTimeout(function() { $("#v").val(1 + Math.floor(Math.random()*98)); }, 500); // randomized for next click between [1..99}
}

function extractmax(callback) {
  if (isPlaying) stop();
  commonAction(hw.extractMax(true, callback), "提取最大值");
}

function heapsort(callback) {
  if (isPlaying) stop();
  commonAction(hw.heapSort(callback), "堆排序");
}

var exploreModeData = [];

// This function will be called before entering e-Lecture Mode
function ENTER_LECTURE_MODE() {
  exploreModeData = hw.saveArray();
}

// This function will be called before returning to Explore Mode
function ENTER_EXPLORE_MODE() {
  hw.restoreArray(exploreModeData);
}

// Lecture action functions
function CUSTOM_ACTION(action, data, mode) {
  if (action == 'random_insert') {
    hideSlide(function() {
      insert(showSlide);
    });
  }
  else if (action == 'insert_top') {
    hideSlide(function() {
      insert_top(showSlide);
    });
  }
  else if (action == 'extractmax') {
    hideSlide(function() {
      extractmax(showSlide);
    });
  }
  else if (action == 'createN') {
    hideSlide(function() {
      createNWithInput(data, showSlide);
    });
  }
  else if (action == 'createNlogN') {
    hideSlide(function() {
      createNlogNWithInput(data, showSlide);
    });
  }
  else if (action == 'heapsort') {
    hideSlide(function() {
      heapsort(showSlide);
    });
  }
}
</script>
</body>
</html>
